package Sort;

import java.util.Arrays;

public class MergeSort {
    public void operation(int[] arr) {
        operation(arr, 0, arr.length - 1);
    }

    public void operation(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        operation(arr, left, mid);
        operation(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }

    //合并数组
    private void merge(int[] arr, int left, int mid, int right) {
        int[] tmpArr = new int[right - left + 1];

        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;

        while (cur1 <= mid && cur2 <= right) {
            if (arr[cur1] < arr[cur2]) {
                tmpArr[i++] = arr[cur1++];
            } else {
                tmpArr[i++] = arr[cur2++];
            }
        }

        while (cur1 <= mid) {
            tmpArr[i++] = arr[cur1++];
        }

        while (cur2 <= right) {
            tmpArr[i++] = arr[cur2++];
        }

        for (int j = 0; j < tmpArr.length; j++) {
            arr[j + left] = tmpArr[j];
        }
    }

    //非递归
    public void operationNor(int[] arr) {
        int gap = 1;

        while (gap <= arr.length) {
            for (int i = 0; i < arr.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= arr.length) {
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                if (right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};

        MergeSort mergeSort = new MergeSort();
        mergeSort.operationNor(arr);
        System.out.println(Arrays.toString(arr));
    }
}
